B-Tree

再來要介紹一個非常常用的 index 結構 B-Tree 和它會用到 storage engine (儲存引擎) page-oriented ，

B-Tree index 幾乎所有的 realtional 資料庫都有用到，像 SSTable 一樣，B-Tree 保留 key-value 組合且也是用 key 做排序，另外也支援範圍搜尋，但 B-Tree 的設計哲學就跟 SSTable 非常不一樣了，前幾天所講的 log-structured + Hash index 最後是存成大小會變動 segment logs，而 B-Tree 是存成大小 固定 的 blocks 或 pages ，通常是 4 KB (有些會更大)，一次只讀一個 page，這種設計哲學也接近有著固定大小磁區 (block) 的傳統硬碟。

每一個 page 都能記錄位置參照，類似 C 的指標，但不是記憶體，而是硬碟中的位置，我們用這些位置參照建成一個 page 樹，如下圖：

假設現在想找 key 為 251 的值，我們就從最上面的 root page 開始找，每一個 key 代表了一段範圍的 child pages，所以找到了 key 200 的參照，再依此類推直到到達 leaf page ， 這裡就有我們的答案了 (或者找不到該值)，leaf page 也代表了最小段的範圍。

B-Tree page 的參照數量稱為 branching factor (分支因子) ，上圖 3-6 的 branching factor 就是為 6， 實務上該值需考量系統需要多少空間存參照和上下界會到哪裡，通常是幾百個。

如果你想更新既有的 key-value，一樣找到 leaf page 後直接寫入硬碟即可；如果想新增 key-value，就會找到包含該 key 範圍的 page 後新增，可是若新增時發生 branching factor 滿了的情形該怎辦？我們會把滿了的那 page 分成 2 個半滿的 page，然後新增該值，如下圖模擬：

B-Tree 演算法能確保樹是平衡的，B-Tree 有 n 個 key 通常深度是 log n ，這代表了你不用找太多的 page 參照就能找到你的資料，大多數的資料庫只要 3-4 層就打死了 (4 層的樹，每個 page 4 KB，branching factor 為 500 的話最高可儲存 256 TB)。

B-Trees 的可靠性 (reliable)

B-Tree 的寫入基本上是覆蓋資料，寫入時是有機會整顆樹的參照不會變動，跟用 log-structured 的 LSM-Trees 比起來完全相反，LSM-Trees 完全不會修改資料，之前有提到 B-Tree 的寫資料的概念跟傳統硬碟類似，傳統硬碟在寫資料時有把磁頭移到正確的位置，然後等旋轉中的碟片轉到正確區域時，覆蓋該磁區的資料；

然而，有些 B-Tree 有時會需要覆寫多個不同的 page，例如前一小節的範例，我們的 branching factor 滿了需要分開它們成 2 個 page 時也需要覆寫父 page 的參照，此時若資料庫掛掉了，就會有不正確的 index 或孤兒 page，這個解法一般都是再新增一個額外的資料結構，在修改 page 樹的參照前會先寫到該檔案 (沒錯又是 append-only log)，確保資料庫掛掉恢復時能回到正確的狀態。

另一個更新 page 時要留意的點是並行控制 (concurrency control)，一次可能會有多個執行緒覆蓋資料，一個簡單的方法是會使用 latches (輕量的鎖) 保護資料，這一點 log-structured 就單純多了。

B-Tree 的優化 (Optimizations)

只提 2 點我覺得重要的：

• 儲存 key 時，可以不用存全部的值 (只要確保不會重複)，這點在我們 ETtoday 使用 Redis 特別有用，將原本 32 長度的 ID 縮短為 10 碼，節省了一半以上的空間，B-Tree 節省空間也就代表會有更多的 branching factor ，樹的深度也可以降低一些些。
• 一般來說，page 可以存在硬碟的任何地方，並無規定臨近的 key， pages 也要存在附近，可是存附近對範圍查詢會比較有效率，一些 B-Tree 的實做會特別把 leaf page 放在連續型的資料空間裡，反之此種實做面對樹的成長就比較麻煩了，這一點 LSM-Trees 就好多了，大型的 segment logs 的可以讓臨近的 key 在硬碟中是靠近的。

B-Tree v.s. LSM-Trees

LSM-Trees 的寫入較 B-Tree 快，而 B-Tree 則是讀取比 LSM-Trees 快，LSM-Trees 讀取較慢是因為通常會需要讀取數個 SSTables，接下來就來聊聊比較儲存引擎 (storage engine) performance 時可以比較的點：

• 寫入

  在寫入作業很重的資料庫下，LSM-Trees 的寫入效率會比 B-Tree 好且次數也較少，SSD 可能會有寫入放大 (write amplification) 的問題，意即寫入的物理資料量變多倍，因此 B-Tree 這種會比較常覆蓋樹資料的結構對 SSD 是稍稍傷的，LSM-Trees 做完 compaction (壓實) 後就寫這麼一次到 SSD 上，更少的寫入也代表它有更多的磁碟寬頻 (disk bandwidth) 可用，連續型的寫入也一定比隨機寫入快；另外 LSM-Trees 的壓縮較好，因為檔案都比 B-Tree 小。

• 硬碟資源碰撞

  硬碟資源是有限的，所以 LSM-Trees 很有可能會有些 request 會需要等待 compaction 做完，雖然 response time 很小，但在高 QPS 查詢情況下，LSM-Trees response time 會被拉高，相比之下 B-Tree 比較可控，好預測。

• 交易性 (transactional)

  B-Tree 的好處是每一個 index 的 key 只會出現一次，不像 LSM-Trees 可能會在多個 semgnet log 有重複的 key，許多的 relational 資料庫對 transactional 很重視，這也讓 B-Tree index 變的很吸引人，交易隔離 (transaction isolation) 實現需要對一個範圍的 key 做 lock，而 B-Tree 可以讓 lock 直接加到樹裡面，有機會的話這 30 天內說不定會講到這點。

新的資料庫越來越流行使用 log-structured index，這裡依舊沒有簡單的規則比較出誰比較好，在不同的情境下，都值得你做許多的測來找出哪個適合你。